/*
实验15-1~2 0-1背包问题
分数 30
作者 陈越
单位 浙江大学

0-1背包问题的定义是：给定一个总承重量为 W 的背包和 n 件物品的集合
S={s1​,⋯,sn​}，其中第 i 件物品有其重量 wi​ 和价值 vi​。要求一种分派方案
x
=(x1​,⋯,xn​)，在满足约束条件 R:
Σi=1n​xi​⋅wi​≤W（即装入的物品总重量不超过背包承重）的前提下，使优化函数
f(x

)=Σi=1n​xi​⋅vi​ 取极大值（即装入的物品总价值最大）。其中 xi​
是整数，取值或为 1 或为 0，即每一件物品只有 2
种选择，或者完全放进背包，或者被完全舍弃。

试用回溯剪枝算法和分支限界算法分别解决 0-1 背包问题。
函数接口定义：

ElemSet Knapsack01(ElemSet W, Objects s, int *x, int n);

其中各种数据类型的定义如下：

typedef double ElemSet; // 物品重量和价值均为实数
#define eps (1e-9) // 当实数的绝对值小于eps时，可认为是0.0
typedef struct ObjNode *Objects;
struct ObjNode {
    ElemSet w;  // 重量
    ElemSet v;  // 价值
};

函数接口定义中，W 是背包总承重量，s 是存储物品集合的数组，x
是待求的分派方案数组，n 是物品数量。要求函数 Knapsack01 求出 0-1
背包问题的最优解，将最优分派方案存在 x 数组中，并返回优化函数的极大值。题目保证
n 不超过 20，所有物品的总重量和总价值均不超过 10^10。

输入样例：

5 11.8
1.1 2.1 5.35 6.24 7.2
1.5 6.3 18.13 22.7 28.8

输出样例：

40.83
( 0 0 1 1 0 )
*/

#include <memory.h>
#include <stdio.h>
#include <stdlib.h>

typedef enum { false, true } bool;
typedef double ElemSet; /* 物品重量和价值均为实数 */
#define eps (1e-9)      /* 当实数的绝对值小于eps时，可认为是0.0 */
typedef struct ObjNode *Objects;
struct ObjNode {
    ElemSet w; /* 重量 */
    ElemSet v; /* 价值 */
};

ElemSet Knapsack01(ElemSet W, Objects s, int *x, int n);

int main(void) {
    Objects s;
    ElemSet W;
    int *x;
    int n, i;

    scanf("%d %lf", &n, &W);
    s = (Objects)malloc(sizeof(struct ObjNode) * n);
    x = (int *)malloc(sizeof(int) * n);
    memset(x, 0, sizeof(int) * n);
    for (i = 0; i < n; i++) {
        scanf("%lf", &s[i].w);
    }
    for (i = 0; i < n; i++) {
        scanf("%lf", &s[i].v);
    }
    printf("%.2f\n", Knapsack01(W, s, x, n));
    printf("( ");
    for (i = 0; i < n; i++) {
        printf("%d ", x[i]);
    }
    printf(")\n");

    return 0;
}

/* 你的代码将被嵌在这里 */
ElemSet max_value = 0.0; // 记录最大价值
int *best_x = NULL;      // 记录最优解

void backtrack(int i, ElemSet current_weight, ElemSet current_value, ElemSet W, Objects s, int *x, int n) {
    if (i == n) {
        // 到达叶子节点，更新最优解
        if (current_value > max_value) {
            max_value = current_value;
            memcpy(best_x, x, sizeof(int) * n);
        }
        return;
    }

    // 剪枝：如果当前重量加上当前物品的重量不超过背包容量
    if (current_weight + s[i].w <= W + eps) {
        x[i] = 1; // 选择当前物品
        backtrack(i + 1, current_weight + s[i].w, current_value + s[i].v, W, s, x, n);
        x[i] = 0; // 回溯
    }

    // 不选择当前物品
    backtrack(i + 1, current_weight, current_value, W, s, x, n);
}

ElemSet Knapsack01(ElemSet W, Objects s, int *x, int n) {
    max_value = 0.0;
    best_x = (int *)malloc(sizeof(int) * n);
    memset(best_x, 0, sizeof(int) * n);

    backtrack(0, 0.0, 0.0, W, s, x, n);

    memcpy(x, best_x, sizeof(int) * n);
    free(best_x);
    return max_value;
}